15.13.2 - 堆（Heap）.md

堆（Heap）

在服务器程序开发中经常要用到排序功能，如会员积分榜。普通的array数据结构，使用sort进行排序，即使使用了最快的快速排序方法，实际上也会存在较大的计算开销。因此在内存中维护一个有序的内存结构可以有效低避免sort排序的计算开销。

在PHP中SplHeap就是一种有序的数据结构。数据总是按照最小在前或最大在前排序。新插入的数据会自动进行排序。

定义

SplHeap数据结构需要指定一个compare方法来进行元素的对比，从而实现自动排序。SplHeap类本身是abstract的，不能直接new。

需要编写一个子类，并实现compare方法。

//最大堆
class MaxHeap extends SplHeap
{
    protected function compare($a, $b)
	{
		return $a - $b;
	}
}

//最小堆
class MinHeap extends SplHeap
{
    protected function compare($a, $b)
	{
		return $b - $a;
	}
}

使用

定义好子类后，可使用insert方法插入元素，插入的元素会使用compare方法与已有元素进行对比，自动排序。

$list = new MaxHeap;
$list->insert(56);
$list->insert(22);
$list->insert(35);
$list->insert(11);
$list->insert(88);
$list->insert(36);
$list->insert(97);
$list->insert(98);
$list->insert(26);

• SplHeap底层使用跳表数据结构，insert操作的时间复杂度为O(Log(n))

注意这里只能插入数字，因为我们定义的compare不支持非数字对比。如果要支持插入数组或对象，可重新实现compare方法。

class MyHeap extends SplHeap
{
    protected function compare($a, $b)
	{
		return $a->value - $b->value;
	}
}
class MyObject
{
	public $value;
	
	function __construct($value)
	{
		$this->value = $value;
	}
}

$list = new MyHeap;
$list->insert(new MyObject(56));
$list->insert(new MyObject(12));

使用foreach遍历堆，可以发现是有序输出。

foreach($list as $li)
{
	echo $li."\n";
}